package com.duoduo.剑指Offer;

import java.util.Stack;

/**
 * @program: algorithm
 * @description: 二叉搜索树的后序遍历序列41
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 *  
 *
 * 参考以下这颗二叉搜索树：
 *
 *      5
 *     / \
 *    2   6
 *   / \
 *  1   3
 * 示例 1：
 *
 * 输入: [1,6,3,2,5]
 * 输出: false
 * 示例 2：
 *
 * 输入: [1,3,2,6,5]
 * 输出: true
 *
 * @author: chaidl  ！
 * @create: 2022-05-28 20:53
 */
//[ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。
public class 二叉搜索树的后序遍历序列41 {
	public boolean verifyPostorder(int[] postorder) {
		Stack<Integer> stack = new Stack<>();
		int root = Integer.MAX_VALUE;
		for(int i = postorder.length - 1; i >= 0; i--) {
			if(postorder[i] > root) return false;
			while(!stack.isEmpty() && stack.peek() > postorder[i])
				root = stack.pop();
			stack.add(postorder[i]);
		}
		return true;

	}
}
